1. Field of the Invention
The present invention relates to a content addressable memory or an associative memory comprising a number of word memories each for storing data, and having such a function that match or mismatch between data stored in word memories and retrieval data inputted to the word memories are retrieved.
2. Description of the Related Art
Recently, there has been proposed an associative memory provided with the retrieval function as mentioned above. First, there will be described arrangements and functions of the associative memory, and then examples of the field of application of the associative memory.
FIG. 9 is a circuit block diagram of the conventional associative memory by way of example.
Referring to FIG. 9, an associative memory 10 is provided with a number of word memories 11a, 11b, . . . , 11n each consisting of a 5-bit of serial memory cell by way of example. Further, the associative memory 10 comprises a retrieval register 12 which is arranged to receive and latch a word of retrieval data. A bit pattern of the retrieval data latched in the retrieval register 12 in its entirety or in a part specified is compared with a bit pattern of the portion corresponding to the bit pattern of the latched retrieval data with respect to data stored in each of the word memories 11a, 11b, . . . , 11n. As a result of the comparison, if there are found any of the word memories 11a, 11b, . . . , 11n of which the bit pattern matches with that of the retrieval data, a match signal given by a logic "1" will appear on the associated ones of match lines 14a, 14b, . . . , 14n which are provided in conjunction with the word memories 11a, 11b, . . . , 11n, respectively. On the other hand, a mismatch signal given by a logic "0" will appear on the remaining ones of the match lines 14a, 14b, . . . , 14n.
Assuming that the signals "0", "1", "0", "0", "1" . . . , "0" appear on the flag lines 14a, 14b, . . . , 14n, respectively, these signals are applied to a priority encoder 15. The priority encoder 15 is so arranged to output an address signal AD corresponding to the match line given with a highest priority among the match lines (here, two match lines 14b and 14e) on which the match signal given by a logic "1" appears. Supposing that the priority is higher as alphabet of a suffix of the reference character becomes younger, in this case, the match line 14b is selected as the highest priority match line. Thus, the priority encoder 15 outputs an address signal AD corresponding to the highest priority match line 14b, which address signal AD is applied to an address decoder 16, as occasion demands. The address decoder 16 decodes the received address signal AD and outputs an access signal (here a signal given by a logic "1") to the associated one (here a word line 17b) of word lines 17a, 17b, . . . , 17n which are provided in conjunction with the word memories 11a, 11b, . . . , 11n, respectively. Thus, data stored in the word memory 11b associated with the word line 17b on which the access signal appears is read out to an output data register 18.
As described above, according to the associative memory 10, the contents or data stored in a number of word memories 11a, 11b, . . . , 11n are retrieved using the retrieval data, so that an address of the word memory involved in the data match is generated, and thus it is possible to read out the whole data stored in the word memory.
FIG. 10 is a detailed circuit diagram of one of the word memories in the associative memory.
A word memory 11 comprises five memory cells 11-1, 11-2, . . . , and 11-n each having the same structure. The memory cells 11-1, 11-2, . . . , and 11-n are provided with first inverters 20-1, 20-2, . . . , and 20-n and second inverters 21-1, 21-2, . . . , and 21-n, in pairs such that their outputs are connected to their inputs, respectively. Providing pairs of inverters 20-1 and 21-1; 20-2 and 21-2; . . . ; and 20-n and 21-n permits the memory cells 11-1, 11-2, . . . , and 11-n to store one bit information expressed by logic "1" or logic "0", respectively.
In the memory cells 11-1, 11-2, . . . , and 11-n, the outputs of the first inverters 20-1, 20-2, . . . , and 20-n are connected through N channel transistors 22-1, 22-2, . . . , and 22-n to bit lines 23-1, 23-2, . . . , and 23-n, respectively. Gate electrodes of the transistors 22-1, 22-2, . . . , and 22-n are connected to a word line 24. The outputs of the second inverters 21-1, 21-2, . . . , and 21-n are connected through N channel transistors 25-1, 25-2, . . . , and 25-n to bit bar lines 26-1, 26-2, . . . , and 26-n, respectively. Gate electrodes of the transistors 25-1, 25-2, . . . , and 25-n are also connected to the word line 24. Further, in the memory cells 11-1, 11-2, . . . , and 11-n, there are provided pairs of N channel transistors 27-1 and 28-1; 27-2 and 28-2; . . . ; and 27-n and 28-n, respectively, which are connected in series between the bit lines 23-1, 23-2, . . . , and 23-n and the bit bar lines 26-1, 26-2, . . . , and 26-n, respectively. Gate electrodes of transistors 27-1, 27-2 . . . , and 27-n, as ones of these pairs of transistors 27-1 and 28-1; 27-2 and 28-2; . . . ; and 27-n and 28-n, are connected to the outputs of the first inverters 20-1, 20-2, . . . , and 20-n, respectively; and gate electrodes of other transistors 28-1, 28-2, . . . , and 28-n are connected to the outputs of the second inverters 21-1, 21-2, . . . , and 21-n, respectively.
On the match line 14, there are provided transistors 36-1, 36-2, . . . , and 36-n, which are associated with the word memories 11-1, 11-2, . . . , and 11-n, respectively, and are connected in series with each other. Gate electrodes of the transistors 36-1, 36-2, . . . , and 36-n are connected to points between pairs of transistors 27-1 and 28-1; 27-2 and 28-2; . . . ; and 27-n and 28-n, respectively.
Further, there is provided an additional transistor 36-0 connected in series with the match line 14 which is grounded through the transistor 36-0. A gate electrode of the transistor 36-0 is connected to the control line 30.
Furthermore, there is provided a sensing inverter 31 which is connected with the other end (right hand in FIG. 10) of the match line 14. The match line 14 extends also to the output side of the inverter 31 and is connected therethrough to the priority encoder 15 (refer to FIG. 9).
Between an input of the inverter 31 and the power supply V.sub.DD, there are provided two P-type of transistors 32 and 33. A gate electrode of the P-type of transistor 32 is connected to the control line 30. A gate electrode of the P-type of transistor 33 is connected to an output of the inverter 31.
In the associative memory having the word memories as mentioned above in structure and its peripheral circuits, a match retrieval is conducted in a manner as set forth below.
Assuming that the memory cell 11-1 stores information of a logic "1", the output side of the first inverter 20-1 takes a state of a logic "1", and the output side of the second inverter 21-1 takes a state of a logic "0".
It is assumed that a retrieval for a logic "1" is performed for the above-mentioned memory cell 11-1. That is, the bit line 23-1 is enabled with a logic "1", and the bit bar line 26-1 is enabled with a logic "0". While the word line 24 is kept in a state of a logic "0". Since a logic level "1" of voltage is applied to the gate electrode of the transistor 27-1, and a logic level "1" of signal on the bit line 23-1 is applied to the gate electrode of the transistor 36-1, the transistor 36-1 turns on. That is, when the bit information stored in the memory cell 11-1 and the bit information in the retrieval data entered through the bit line 23-1 and the bit bar line 26-1 are equivalent to each other, the associated transistor 36-1 turns on.
Assuming that the memory cell 11-2 stores information of a logic "0", the output side of the first inverter 20-2 takes a state of a logic "0", and the output side of the second inverter 21-2 takes a state of a logic "1".
It is assumed that a retrieval for a logic "1" is also performed for the above-mentioned memory cell 11-2. That is, the bit line 23-2 is enabled with a logic "1", and the bit bar line 26-2 is enabled with a logic "0". In this case, a logic level "0" of signal on the bit bar line 26-2 is applied through the transistor 28-2 to the gate electrode of the transistor 36-2, so that the transistor 36-2 is kept turning off. Thus, in case of the mismatch, the electric charge, which has been precharged on the match line 14, is not discharged.
With respect to the masked bit, as shown concerning the memory cell 11-n, both the bit line 23-n and the bit bar line 26-n are enabled with the logic "1". In this case, either the transistor 27-n or the transistor 28-n turns on in accordance with the fact that the memory cell 11-5 has stored logic "0" of information or logic "1" of information, so that the transistor 36-n turns on in any way.
To conduct a retrieval, first, the control line 30 is enabled with "0", so that a transistor 32 turns on whereby a match line 14 at the input side of the inverter 31 is precharged. Thereafter, the control line 30 is enabled with "1", so that the transistor 32 turns off to stop the precharge and the transistor 36-0 turns on.
In this case, when data stored in the memory cells 11-1, 11-2, . . . , and 11-n, which memory cells constitute the word memory 11, match with the entered retrieval information throughout the memory cells (as mentioned above, the masked bit is regarded as a "match"), all of the transistors 36-1, 36-2, . . . , and 36-n turn on, so that the electric charge, which has been precharged on the match line 14, is discharged. Thus, the inverter 31 outputs a logic "1" of signal.
Incidentally, it is noted that FIG. 10 merely shows by way of example the memory structure of the associative memory, and there are proposed various types of structure (See, for example, Japanese Patent Application No. 216424/1993).
Next, there will be described an example of application of the associative memory to a LAN (Local Area Network) hereinafter.
FIGS. 11(A)-11(C) are each a view showing an example of the LAN.
As shown in FIG. 11(A), it is assumed that coupled to two communication lines LAN 1 and LAN 2 are a plurality of terminals A-G, and T-Z, respectively to constitute two communication networks. Further, it is assumed that traffic volume of each of the communication lines LAN 1 and LAN 2, that is, quantity of data transmitted via the communication line, or a degree of congestion of the communication line, is given with "10".
When there occurs a necessity for connecting these two communication lines to each other, if they are simply connected to each other, as shown in FIG. 11(B), then the traffic volume of the communication lines LAN 1 and LAN 2 becomes 20. This involves such a result that the communication lines are dramatically congested, so that the connection among the terminals becomes more difficult, thereby increasing waiting time and idle time.
Hence, usually, as shown in FIG. 11(C), connected between the communication lines LAN 1 and LAN 2 is a bridge for performing filtering as to whether or not data originated from one of the communication lines LAN 1 and LAN 2 is transmitted to the other. When the bridge is connected, assuming that traffic volume of data passing through the bridge, that is, traffic volume as to transfer of data bridging two communication lines LAN 1 and LAN 2, is "1", adding traffic volume "10" of the interior of each of the communication lines LAN 1 and LAN 2, traffic volume of each of the communication lines LAN 1 and LAN 2 becomes "11". Thus, traffic volume is extremely decreased in comparison with the case, as shown in FIG. 11(B), in which two communication lines LAN 1 and LAN 2 are simply connected to each other. Here, while there has been described the connection between two communication lines LAN 1 and LAN 2, connection of a number of communication lines to the bridge may enhance the difference in the traffic.
FIG. 12 is an illustration useful for understanding the function of the bridge.
The bridge includes a memory. First, starting with a null state, for example, when data is transmitted from the terminal A of the communication line LAN 1, upon receipt of the data from the communication line LAN 1 end, the bridge learns that the terminal A is connected to the communication line LAN 1. This learning is conceptually implemented in such a manner that the memory inside of the bridge is provided with table 1 and table 2, which are associated with the communication lines LAN 1 and LAN 2, respectively, and the terminal A is written into the table 1 associated with the communication line LAN 1. At the time point of the learning of the terminal A, it is not determined whether or not the receiving destination of the data transmitted from the terminal A resides in the communication network involved in the LAN 1 end, and thus at this time point the data is allowed to pass through unconditionally the bridge.
Repeat of the above-mentioned learning makes it possible to build table 1 and table 2, as shown in FIG. 12, in the bridge. After these tables have been built, for example, as shown in the figure, data which is involved in terminal B (the LAN 1 end) as a transmitting source and terminal X (LAN 2end) as a receiving destination, is allowed to pass through the bridge, upon recognition by the bridge of the fact that the terminals B and X are located at opposite sides over the bridge each other. On the other hand, in a case where the transmitting source and the receiving destination are denoted by terminals A and E both belonging to the LAN 1 end, data is inhibited from passing through the bridge, upon recognition by the bridge of the fact that the terminals A and E reside in the communication network which is located at the same side looking from the bridge. This scheme contributes to reduction of traffic volume.
Adopting an associative memory as the memory used in the bridge as mentioned above may contribute to a high speed processing. For example, the associative memory is used to store information concerning the respective terminals A-G and T-Z, and further information as to whether each of those terminals belongs to table 1 (being connected to the LAN 1 end) or table 2 (being connected to the LAN 2 end). To determine whether or not data is allowed to pass through the bridge, for example, in a case where the receiving destination is given with terminal X, the retrieval is performed using "X" as retrieval data, and it is recognized that "X" is a terminal belonging to table 2 (LAN 2). In this manner, it may be determined whether or not data is allowed to pass through the bridge.
On the contrary, the bridge is equipped with the conventional RAM or the like, there are needs to read out one by one data stored and retrieve the data through sequential comparison to identify as to whether or not the read data is involved in the terminal X. Thus, in this case, a lot of time will be required for determination as to allowance of passage of data through the bridge or inhibition of the data.
As described above, the associative memory may be preferably used in, for example, a LAN network and the like. Whereas, for example, when data is transmitted from the terminal A, it is confirmed whether the terminal A is already registered in the memory of the bridge, and if not it is necessary to register the terminal A. In this manner, hitherto, there are needed two steps, one of which is involved in the confirmation of registration, and another the implementation of registration in case of not registered. This hinders higher speed operation of the bridge.